#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <queue>

/*
 * Dijkstra algorithm
 *
 */
#define N 1003				// max number of nodes
#define INF 0x3f3f3f3f			// a infinity representation

using namespace std;

typedef pair < int, int > ii;		// struct to represent the node label (int) and its distance (int)

vector <int> graph[N], weight[N];	// graph representation (a vector for the adjacents and a vector for the weights)
int dis[N][N];				// matrix of min distance (from vertex i to all others)

					// a priority queue to run faster
priority_queue < ii , vector < ii >, greater < ii > > q;
				
/*
 * Params:	'source' node,
 * 		'distance' vector (where the result of min distance from 'source' to all others),
 * 		number of nodes in the graph ('n')
 */ 
void dijkstra(int source, int * distance, int n)
{
	for(int i = 1; i <= n; i++)
		distance[i] = INF;

	distance[source] = 0;
	q.push( make_pair ( distance[source], source ) );
	
	while(!q.empty()) {
		int cur = q.top().second;
		int disCur = q.top().first;
		q.pop();

		if( disCur > distance[cur] ) continue;

		for(int i = 0; i < graph[cur].size(); i++) {
			int u = graph[cur][i];
			int w = weight[cur][i];
		
			if( distance[u] > disCur + w) {
				distance[u] = disCur + w;
				q.push( make_pair( distance[u], u ));
			}
		}
	}
}

int main (int argc, char ** argv)
{
	int n, m;
	int a, b, c;

	// Read the input 
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b >> c;

		graph[a].push_back(b);
		graph[b].push_back(a);
		weight[a].push_back(c);
		weight[b].push_back(c);
	}

	// for all nodes, run the dijkstra
	int ans = INF, local;
	for(int i = 1; i <= n; i++) {
		dijkstra(i, dis[i], n);

		local = 0;
		// for 'i' node gets the most far 
		for(int j = 1; j <= n; j++) {
			if( dis[i][j] != INF ) 
				local = max(local, dis[i][j]);
		}
		// if 'i' has smaller most far node, then get it as answer
		ans = min(ans, local);
	}

	cout << ans << "\n";

	return 0;
}
